package Other;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class leet_56 {
    public static void main(String[] args) {
        int[][] intervals = new int[4][2];
        intervals[0] = new int[]{3, 4};
        intervals[1] = new int[]{1, 4};
        intervals[2] = new int[]{0, 4};
        intervals[3] = new int[]{5, 4};

        Solution_56 p =new Solution_56();

        p.merge(intervals);

    }

}

class Solution_56 {
    public int[][] merge(int[][] intervals) {
        int[][] result = SortMerge(intervals);
        return result;
    }

    /**
     * 排序解决
     * 1.首先对int[] 里面第一个左区间排序
     * 2.在for循环做对比合并
     *
     * @param intervals
     * @return
     */
    public int[][] SortMerge(int[][] intervals){
        if(intervals.length==0){
            return new int[0][2];
        }
        // 排序
        int[][] sortIntervals = intSort(intervals);

        // 合并
        List<int[]> list = new ArrayList<>();
        list.add(sortIntervals[0]);

        for(int i=1; i<sortIntervals.length; i++){
            int listMaxIndex=list.size()-1;

            int[] now = sortIntervals[i];
            int[] yester = list.get(listMaxIndex);
            if(yester[1]>=now[0]){
                // 如果2个相等 代表需要合并区间
                int maxRight = Math.max(now[1], yester[1]);
                list.remove(listMaxIndex);
                list.add(new int[]{yester[0], maxRight});
            }else{
                // 只有可能now大于yes
                list.add(now);
            }
        }
        return list.toArray(new int[list.size()][]);
    }

    /**
     * 实现数组的排序
     * @param intervals
     * @return
     */
    public int[][] intSort(int[][] intervals){
        for(int i=0; i<intervals.length; i++){
            // 最大的数组
            int[] maxInt = intervals[0];
            int maxIndex = 0;

            // 排好序的不需要动
            for(int j=0; j<intervals.length-i; j++){
                int[] tmpInt = intervals[j];
                if(maxInt[0] < tmpInt[0]){
                    maxInt = tmpInt;
                    maxIndex = j;
                }
            }
            // 找到的最大的放到末尾的交换
            int tailIndex = intervals.length-1-i;

            intervals[maxIndex]=intervals[tailIndex];
            intervals[tailIndex]=maxInt;
        }
        return intervals;
    }
}
